package 代码随想录_动态规划.子序列问题.连续;

/**
 * @author zx
 * @create 2022-06-05 10:17
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
 * 2.确定递推公式
 *  如果 nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度
 *  一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。
 * 即：dp[i + 1] = dp[i] + 1;
 * 注意这里就体现出和动态规划：300.最长递增子序列的区别！
 * 因为本题要求连续递增子序列，所以就必要比较nums[i + 1]与nums[i]，
 * 而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。
 * 既然不用j了，那么也不用两层for循环，本题一层for循环就行，比较nums[i + 1] 和 nums[i]。
 * 3.dp数组如何初始化
 *  以下标i为结尾的数组的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
 * 所以dp[i]应该初始1;
 * 4.确定遍历顺序
 *   dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。
 * 5.举例推导dp数组
 *
 */
public class 最长连续递增序列_674 {

    public int findLengthOfLCIS2(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 1;
        for(int i = 0;i < dp.length;i++) dp[i] = 1;
        for(int i = 1;i < dp.length;i++){
            if(nums[i] > nums[i - 1]){
                dp[i] = dp[i - 1] + 1;
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i = 0;i < nums.length;i++) dp[i] = 1;
        int res = 1;// 连续子序列最少也是1
        for(int i = 0;i < nums.length - 1;i++){
            if(nums[i + 1] > nums[i]){
                dp[i + 1] = dp[i] + 1;
            }
            res = Math.max(res,dp[i + 1]);
        }
        return res;
    }

    /**
     * 最长连续递增序列变种：2025年高德社招,让把这个最长连续递增序列返回
     */
    public static int[] findLengthOfLCIS3(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i = 0;i < dp.length;i++) dp[i] = 1;
        int res = 1;
        int left = 0, right = 0;
        for(int i = 1;i < dp.length;i++){
            if(nums[i] > nums[ i - 1]){
                dp[i] = dp[i - 1] + 1;
            }
            if(dp[i] > res) {
                res = dp[i];
                right = i;
                left = i - res + 1;
            }
        }
        // 思路：一个right变量存储最长连续递增序列的右边界，知道了右边界和最长连续递增序列的长度,就可以计算出left
        // 遍历原数组的left指right,收集结果并返回
        int[] arr = new int[right - left + 1];
        int k = 0;
        for(int i = left;i <= right;i++){
            arr[k] = nums[i];
            k++;
        }
        return arr;
    }
}
